Abstract
Whole program paths (WPP) are a new approach to capturing and representing a program's dynamic---actually executed---control flow. Unlike other path profiling techniques, which record intraprocedural or acyclic paths, WPPs produce a single, compact description of a program's entire control flow, including loop iteration and interprocedural paths.This paper explains how to collect and represent WPPs. It also shows how to use WPPs to find hot subpaths, which are the heavily executed sequences of code that should be the focus of performance tuning and compiler optimization.
- 1 G. Ammons, T. Ball, and J. R. Larus, "Exploiting Hardware Performance Counters with Flow and Context Sensitive Profiling," in Proceedings of the SIGPLAN '97 Conference on Programming Language Design and Implementation. Las Vegas, NV, 1997, pp. 85-96. Google ScholarDigital Library
- 2 G. Ammons and J. R. Larus, "Improving Data-flow Analysis with Path Profiles," in Proceedings of the SiGPLAN '98 Conference on Programming Language Design and Implementation. Montreal, Canada, 1998, pp. 72-84. Google ScholarDigital Library
- 3 S. Andler, "Predicate Path Expressions," in Proceedings of the Sixth Annual A CM Symposium on Principles of Programming Languages. San Antonio, Texas, 1979, pp. 226-236. Google ScholarDigital Library
- 4 B. S. Baker, "Parametefized Duplication in Strings: Algorithms and an Application to Software Maintenance," SIAM Journal of Computing, vol. 26, pp. 1343-I 362, 1995. Google ScholarDigital Library
- 5 V. Bala, "Low Overhead Path Profiling," Hewlett Packard Labs 1996.Google Scholar
- 6 T. Ball and J. R. Larus, "Efficient Path Profiling," in Proceedings of the 29th Annual iEEEdACM International Symposium on Microarchitecture. Paris, France, 1996, pp. 46-57. Google ScholarDigital Library
- 7 T. Ball, P. Mataga, and M. Sagiv, "Edge Profiling Versus Path Profiling: the Showdown," in Proceedings of the 25th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. San Diego, CA, 1998, pp. 134- 148. Google ScholarDigital Library
- 8 R. Bodik, R. Gupta, and M. L. Sofia, "Refining Data Flow Information using Infeasible Paths," in Proceedings of the A CM SIGSOFT Fifth Symposium on the Foundations of Software Engineering. Zurich, Switzerland, 1997. Google ScholarDigital Library
- 9 I.-C. K. Chen, J. T. Coffey, and T. N. Mudge, "Analysis of Branch Prediction via Data Compression," in Proceedings of the Seventh International Conference on Architectural Support for Programming Languages and Operating Systems. Cambridge, MA, 1996, pp. 128-137. Google ScholarDigital Library
- 10 E. N. Clarke, E. A. Emerson, and A. P. Sistla, "Automatic Verification of Finite-State Concurrent Systems Using Temporal Logic Specifications," A CM Transactions on Programming Languages and Systems, vol. 8, pp. 244-263, 1986. Google ScholarDigital Library
- 11 J. A. Fisher, "Trace Scheduling: A Technique for Global Microeode Compaction," IEEE Transactions on Computers, vol. C-30, pp. 478-490, 1981.Google Scholar
- 12 J. A. Fisher, J. R. Ellis, J. C. Ruttenber g, and A. Nicolau, "Parallel Processing: A Smart Compiler and a Dumb Machine," in Proceedings of the A CM SiGPLAN '84 Symposium on Compiler Construction. Montreal, Canada, 1984, pp. 37-47. Google ScholarDigital Library
- 13 J. Gray, "The Benchmark Handbook for Database and Transaction Processing Systems," in The Morgan Kaufmann Series in Data Management Systems, J. Gray, Ed., second ed. San Francisco: Morgan Kaufmann, 1993.Google Scholar
- 14 R. Gupta, D. A. Berson, and J. Z. Fang, "Path Profile Guided Partial Dead Code Elimination Using Predication," in Proceedings of the International Conference on Parallel Architecture and Compilation Techniques (PACT). San Francisco, CA, 1997. Google ScholarDigital Library
- 15 Q. Jacobson, E. Rotenberg, and J. E. Smith, "Path-Based Next Trace Prediction," in Proceedings of the 30th Annual IEEE/ACM International Symposium on Microarchitecture. Research Triangle Park, NC, 1997. Google ScholarDigital Library
- 16 J. R. Larus, "Abstract Execution: A Technique for Efficiently Tracing Programs," Software--Practice and Experience, vol. 20, pp. 1241-1258, 1990. Google ScholarDigital Library
- 17 J. R. Larus and E. Schnarr, "EEL: Machine-independent Executable Editing," in Proceedings of the SiGPLAN '95 Conference on Programming Language Design and Implementation. La Jolla, CA, 1995, pp. 291-300. Google ScholarDigital Library
- 18 D. Melski and T. Reps, "Interprocedural Path Profiling," Computer Sciences Department, University of Wisconsin- Madison, Technical Report TR- 1382, September 1998.Google Scholar
- 19 D. Melski and T. Reps, "Interprocedural Path Profiling," in Proceedings of CC '99: 8th International Conference on Compiler Construction. Amsterdam, The Netherlands, 1999. Google ScholarDigital Library
- 20 D. Mosberger and L. L. Peterson, "Making Paths Explicit in the Scout Operating System," in Proceedings of the Second USENIX Symposium on Operating Systems Design and Implementation (OSDI). Seattle, WA, 1996, pp. 153-167. Google ScholarDigital Library
- 21 C. G. Nevill-Manning and I. H. Witten, "Compression and explanation using hierarchical grammars," The Computer Journal, vol. 40, pp. 103-116, 1997.Google ScholarCross Ref
- 22 C. G. Nevill-Manning and I. H. Witten, "Linear-time, incremental hierarchy inference for compression," in Proceedings of the Data Compression Conference (DCC '97). Snowbird, UT: iEEE Computer Society, 1997, pp. 3-1 I. Google ScholarDigital Library
- 23 A. R. Pleszkun, "Techniques for Compressing Program Address Traces," in Proceedings of the 27th Annual IEEE/A CM International Symposium on Mi croarchitecture, 1994, pp. 32-40. Google ScholarDigital Library
- 24 C. Pu, T. Autrey, A. Black, C. Consel, C. Cowan, J. Inouye, L. Kethana, J. Walpole, and K. Zhang, "Optimistic Incremental Specialization: Streamlining a Commercial Operating System," in Proceedings of the Fifteenth A CM Symposium on Operating System Principles. Copper Mountaint Resort, CO, 1995, pp. 314-324. Google ScholarDigital Library
- 25 E. Rotenberg, S. Bennett, and J. E. Smith, "Trace Cache: a Low Latency Approach to High Bandwidth Instruction Fetching," in Proceedings of the 29th Annual IEEE/ACM International Symposium on Microarchitecture. Paris, France, ! 996, pp. 24-34. Google ScholarDigital Library
- 26 E. Rotenberg, Q. Jacobson, Y. Sazeides, and J. Smith, "Trace Processors," in Proceedings of the 30th Annual iEEE/A CM International Symposium on Microarchitecture. Research Triangle Park, NC, 1997, pp. 138-148. Google ScholarDigital Library
- 27 A. Srivastava and A. Eustace, "ATOM A System for Building Customized Program Analysis Tools," in Proceedings of the SIGPLAN '94 Conference on Programming Language Design and Implementation. Orlando, FL, 1994, pp. 196-205. Google ScholarDigital Library
- 28 C. Young, N. Gloy, and M. D. Smith, "A Comparative Analysis of Schemes for Correlated Branch Prediction," in Proceedings of the 22nd Annual International Symposium on Computer Architecture, 1995, pp. 276-286. Google ScholarDigital Library
Index Terms
- Whole program paths
Recommendations
Whole program paths
PLDI '99: Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementationWhole program paths (WPP) are a new approach to capturing and representing a program's dynamic---actually executed---control flow. Unlike other path profiling techniques, which record intraprocedural or acyclic paths, WPPs produce a single, compact ...
Profiling all paths: A new profiling technique for both cyclic and acyclic paths
As an important technique in dynamic program analysis, path profiling collects the execution frequency of different paths, and has been widely used in a variety of areas. However, existing intra-procedural profiling techniques cannot effectively deal ...
A Technique of Profiling Selective Paths
COMPSAC '11: Proceedings of the 2011 IEEE 35th Annual Computer Software and Applications ConferencePath profiling records the frequency of each path in an executed routine. To accomplish profiling, probes are instrumented in a program and executed as the program runs. So the number of probes has important influences on the efficiency of a profiling ...
Comments